package leetcode.D200.T146;

import java.util.*;

/**
 * @File Info: leetcode -- <LRUCache>
 * @Author: 18362
 * @Create: 2022-03-10 23:47:07 星期四
 */

class LRUCache {

    // 方法1：借助LinkedHashMap，需要重写removeEldestEntry方法
    /*private int capacity;
    private LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<Integer, Integer>(capacity, 1, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return cache.size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }*/

    // 方法二：手动实现双向链表+哈希表
    static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        Node() {}
        Node (int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    static class DoubleList {
        Node head, tail;
        int size;
        DoubleList() {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
            size = 0;
        }
        int size() {return size;}

        void addLast(Node x) {
            x.prev = tail.prev;
            tail.prev = x;
            x.next = tail;
            x.prev.next = x;
            size++;
        }

        int removeFirst() {
            if (size == 0)
                return 0;
            head = head.next;
            head.prev = null;
            size--;
            return head.key;
        }

        void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }
    }

    private DoubleList list;
    private Map<Integer, Node> map;
    private int capacity;

    public LRUCache(int capacity) {
        list = new DoubleList();
        map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        Node x = map.get(key);
        makeRecent(x);
        return x.value;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)) {
            Node x = new Node(key, value);
            if (capacity == list.size()) {
                int k = list.removeFirst();
                map.remove(k);
            }
            list.addLast(x);
            map.put(key, x);
        } else {
            Node x = map.get(key);
            x.value = value;
            makeRecent(x);
        }
    }

    private void makeRecent(Node node) {
        list.remove(node);
        list.addLast(node);
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */